package lc;

import ch2linkedlist.Chapter;
import ch2linkedlist.ListNode;

public class ReorderList {

//	public void reorderList(ListNode head) {
//    	int count = 0;
//    	ListNode n = head;
//    	while (n != null) {
//    		count++;
//    		n = n.next;
//    	}
//    	
//    	if (count > 0) {
//    		reorderListRecurse(head, count);    		
//    	}
//		
//	}
//	
//	ListNode reorderListRecurse(ListNode head, int n) {
//		if (head == null) {
//			return null;
//		}
//		else if (n < 2) {
//			return head;
//		}
//		
//		ListNode tailp = head;
//		for (int i=0; i<n-2; i++) {
//			tailp = tailp.next;
//		}
//		ListNode tail = tailp.next;
//
//		tailp.next = null;
//		tail.next = reorderListRecurse(head.next, n-2);
//		head.next = tail;
//		return head;
//	}
	
	public void reorderList(ListNode head){
        if(head == null || head.next == null) return;
        ListNode h = reorderList(head, head, head);
	}

	public ListNode reorderList(ListNode prev, ListNode slow, ListNode faster) {
		if (faster == null || faster.next == null) {
			if (faster != null) {
				ListNode reverse = slow.next;
				slow.next = null;
				return reverse;
			}
			prev.next = null;
			return slow;
		}
		ListNode retNode = reorderList(slow, slow.next, faster.next.next);
		// concanate
		ListNode temp = retNode.next;
		retNode.next = slow.next;
		slow.next = retNode;
		return temp;
	}

	public static void main(String ...strings) {
		ReorderList sol = new ReorderList();
		ListNode head = Chapter.createSampleList(new int [] {1,2,3,4});
		sol.reorderList(head);
		Chapter.print(head);
		
		head = Chapter.createSampleList(new int [] {1, 2});
		sol.reorderList(head);
		Chapter.print(head);
		
		sol.reorderList(null);
	}
}
